// 2022 - 12 - 20 选择排序练习

#include <iostream>
#include <vector>

using namespace std;
namespace MySort
{
    // 基本选择排序  重载了两个函数
    template<class T>
    void SelectSort(vector<T>& v)
    {
        size_t n = v.size();
        int min, max;
        for (size_t i = 0; i < n / 2; ++i)
        {
            max = min = i;
            for (size_t j = i; j < n - i; ++j)
            {
                if (v[min] > v[j]) min = j;
                if (v[max] < v[j]) max = j;
            }
            swap(v[min], v[i]);
            if (max == i) max = min;
            swap(v[max], v[n - i - 1]); 
        }
    }

    template<class T>
    void SelectSort(T* v, size_t n)
    {
        int min, max;
        for (size_t i = 0; i < n / 2; ++i)
        {
            max = min = i;
            for (size_t j = i; j < n - i; ++j)
            {
                if (v[min] > v[j]) min = j;
                if (v[max] < v[j]) max = j;
            }
            swap(v[min], v[i]);
            if (max == i) max = min;
            swap(v[max], v[n - i - 1]); 
        }
    }

    // 堆排
    // 向下调整-大根堆
    template<class T>
    void AdjustDwon(vector<T>& v, size_t n, size_t p)
    {
        if (n > v.size()) return;
        size_t child = p * 2 + 1;

        while (child < n)
        {
            if (v[child + 1] > v[child] && child + 1 < n) child++;
            if (v[child] > v[p]) swap(v[p], v[child]);
            else break;
            p = child;
            child = p * 2 + 1;
        }
    }

    template<class T>
    void HeapSort(vector<T>& v)
    {
        size_t n = v.size();

        // 首先建立大根堆
        for (int i = n - 1; i >= 0; --i)
        {
            AdjustDwon(v, n, i);  // 这里必须是n，因为到时候要调整的数本身位于下方，他是从后向前调整的
        }
        // 利用大根堆选择大数，首尾交换，从头开始向下调整
        for (size_t i = 0; i < n; ++i)
        {
            swap(v[0], v[n - i - 1]);
            AdjustDwon(v, n - 1 - i, 0);
        }
    }
}

int main()
{
    int arr[] = {3, 4, 2, 1, 7};
    vector<int> v = {4, 2, 0, 1, 2, 9, 8};
    // vector<int> v = {3, 2, 1};
    // MySort::SelectSort(v);
    MySort::HeapSort(v);
    for (auto e : v)
    {
        cout << e << " ";
    }
    cout << endl;

    // MySort::SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
    // for (auto e : arr)
    // {
    //     cout << e << " ";
    // }
    // cout << endl;
    return 0;
}